package leetcode.D300.T257;

import util.TreeNode;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new LinkedList<>();
        if(root == null) {
            return result;
        }
        List<TreeNode> temp = new LinkedList<>();
        dfs(root, temp, result);
        return result;
    }
    private void dfs(TreeNode root, List<TreeNode> temp, List<String> result) {
        temp.add(root);
        if(root.left == null && root.right == null) {
            result.add(serialize(temp));
            temp.remove(temp.size()-1);
            return;
        }
        if(root.left != null) {
            dfs(root.left, temp, result);
        }
        if(root.right != null) {
            dfs(root.right, temp, result);
        }
        temp.remove(temp.size()-1);
    }
    private String serialize(List<TreeNode> temp) {
        StringBuilder sb = new StringBuilder();
        int i = 0;
        Iterator<TreeNode> iterator = temp.iterator();
        while(iterator.hasNext()) {
            if(i > 0) {
                sb.append("->");
            }
            sb.append(String.valueOf(iterator.next().val));
            ++i;
        }
        return sb.toString();
    }
}
